package code;

import java.util.ArrayList;


public class TrapRainWater {
    public int trap(int[] A) {
        int ans=0;
        ArrayList<Integer> peekIndex=new ArrayList<>();
        int n=A.length;
        int[] sum=new int[n];
        int i,j,k;
        //找峰值点
        if(n<3)	return ans;
        
        for(i=0;i<n;i++){
        	if(i==0 && A[i]>A[i+1])	peekIndex.add(i);
        	if(i==n-1 && A[i]>A[i-1])	peekIndex.add(i);
        	if(i>0 && i<n-1){
        		if(A[i]>A[i-1] && A[i]>A[i+1] 
        				|| A[i]>A[i-1] && A[i]==A[i+1] 
        				||	A[i]==A[i-1] && A[i]>A[i+1]
        				)
        			peekIndex.add(i);
        	}
        	sum[i]=A[i];
        	if(i>0)	sum[i]+=sum[i-1];
        }
        
        for(i=0;i<peekIndex.size();){
        	/*
        	 * 找第一个比自己大的数
        	 * 如果没找到右边第一个比A[i]大的数，则找右边最大的数
        	 */
        	int max=0;
        	int maxIndex=0;
        	for(j=i+1;j<peekIndex.size();j++){
        		//记录右边最大的一个值
        		if(max<A[peekIndex.get(j)]){
        			max=A[peekIndex.get(j)];
        			maxIndex=j;
        		}
        		if(A[peekIndex.get(i)]<=A[peekIndex.get(j)]){
        			break;
        		}
        	}
        	//x<=y
        	if(j<peekIndex.size()){
        		//还要找到第一个A[k]>=A[peekIndex.get(i)]
        		for(k=peekIndex.get(i)+1;k<=peekIndex.get(j);k++)
        			if(A[peekIndex.get(i)]<=A[k]){
        				break;
        			}
        		ans+=A[peekIndex.get(i)]*(k-peekIndex.get(i)-1);
        		int t1=0;
        		if(k>0)	t1=sum[k-1];
        		int t2=sum[peekIndex.get(i)];
        		ans-=(t1-sum[peekIndex.get(i)]);
        		i=j;
        	}
        	//x>y
        	else{
        	    if(max==0)	break;
        	    //找第一个A[j]>=A[max]的j
        	    for(k=peekIndex.get(maxIndex)-1;k>=peekIndex.get(i);k--){
        	    	if(A[k]>=max)
        	    		break;
        	    }
        		ans+=max*(peekIndex.get(maxIndex)-k-1);
        		int t1=0;
        		if(peekIndex.get(maxIndex)>0)	t1=sum[peekIndex.get(maxIndex)-1];
        		ans-=(t1-sum[k]);
        		i=maxIndex;
        	}
        }
    	return ans;        
    }
    public static void main(String[] args){
    	TrapRainWater rw=new TrapRainWater();
    	int[] ts1={0,1,0,2,1,0,1,3,2,1,2,1};
    	int[] ts={2,6,3,8,2,7,2,5,0};
    	int ans=rw.trap(ts);
    	System.out.println(ans);
    }
}
